CF235E Number Challenge <莫比乌斯反演>

Problem

Number Challenge

Description

Let’s denote as the number of divisors of a positive integer . You are given three integers , and . Your task is to calculate the following sum:

Find the sum modulo .

Input

The first line contains three space-separated integers , and .

Output

Print a single integer — the required sum modulo .

Examples

Input 1

2 2 2

Output 1

Input 2

4 4 4

Output 2

Input 3

10 10 10

Output 3

Note

For the first example.

So the result is .

标签：莫比乌斯反演

Translation

给出三个整数（），求。

Solution

还记得BZOJ3994【SDOI2015】约束个数和吗？这是那道题的加强版本。

做那道题的时候，我们得到了一个重要结论，即。
这个结论可以推广到三维，即

具体证明见rng_68的证明。

然后就可以很笨拙地套路反演将一个化为的和式移到前面了。

令，那么

到这里就可以暴力做了。由于当且仅当互质时才会计算，所以直接暴力计算是可以过这种比较小的数据的。

据说可以做到，不过我不会。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define MOD 1073741824
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
bool NotPri[MAX_N+5];
int cnt, pri[MAX_N+5], mu[MAX_N+5];
int cache[MAX_N+5][MAX_N+5];
int gcd(int a, int b) {
    if (cache[a][b]) return cache[a][b];
    return cache[a][b] = (b ? gcd(b, a%b) : a);
}
void init() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > MAX_N) break;
            NotPri[i*pri[j]] = true;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        }
    }
}
lnt f(int n, int x) {
    lnt ret = 0;
    for (int i = 1; i <= n; i++)
        if (gcd(i, x) == 1) (ret += n/i) %= MOD;
    return ret;
}
int main() {
    int a, b, c; lnt ans = 0;
    read(a), read(b), read(c), init();
    for (int k = 1; k <= c; k++)
        for (int d = 1; d <= min(a, b); d++) if (gcd(d, k) == 1)
            (ans += 1LL*(c/k)*mu[d]%MOD*f(a/d, k)%MOD*f(b/d, k)%MOD) %= MOD;
    return printf("%lld\n", (ans+MOD)%MOD), 0;
}